/**
 * example:
 * (7->2->4->3) + (5->6->4) = (7->8->0->7)
 * @param {ListNode} l1 
 * @param {ListNode} l2 
 * 最高位位于链表开始位置，两数相加返回一个新的链表
 * 要求不能对链表进行翻转
 * 解法：用栈保存信息 
 */
var addTwoNumbers = function (l1, l2) {
    const stack1 = [], stack2 = []
    // 数据入栈
    while (l1 !== null) {
        stack1.push(l1.val)
        l1 = l1.next
    }
    while (l2 !== null) {
        stack2.push(l2.val)
        l2 = l2.next
    }
    // 进位信息
    let carry = 0
    // 当前节点
    let curr = null

    while (stack1.length !== 0 || stack2.length !== 0) {
        let sum = 0
        if (stack1.length !== 0) {
            sum += stack1.pop()
        }
        if (stack2.length !== 0) {
            sum += stack2.pop()
        }
        sum += carry

        const node = new ListNode(sum % 10)
        carry = Math.floor(sum / 10)

        // 逆向添加节点
        node.next = curr
        curr = node
    }
    
    // 检查最后一次进位
    if (carry !== 0) {
        const node = new ListNode(carry)
        node.next = curr
        curr = node
    }

    return curr
}